#include <cstdio>
#include <cstring>

struct BigNum 
{ 
int len, num[ 20 ];
}; 

void operator += ( BigNum &a, const BigNum b ) 
{ 
int i; 
if ( a.len < b.len ) 
{ 
for ( i = 0; i < a.len; i++ ) 
a.num[ i ] += b.num[ i ]; 
for ( i = a.len; i < b.len; i++ ) 
a.num[ i ] = b.num[ i ]; 
a.len = b.len; 
} 
else 
for ( i = 0; i < b.len; i++ ) 
a.num[ i ] += b.num[ i ]; 
for ( i = 0; i < a.len; i++ ) 
if ( a.num[ i ] >= 10000 ) 
{ 
if ( i == a.len - 1 ) 
{ 
a.len++; 
a.num[ i + 1 ] = 0; 
} 
a.num[ i + 1 ] += a.num[ i ] / 10000; 
a.num[ i ] %= 10000; 
} 
} 

int main( )
{
    BigNum f[ 201 ];
    int i, n, l;
    char str[ 201 ];
    for ( i = 1; i <= 200; i++ )
    {
        f[ i ].len = 1;
        f[ i ].num[ 0 ] = 0;
    }
    f[ 1 ].num[ 0 ] = 1;
    f[ 2 ].num[ 0 ] = 2;
    for ( i = 3; i <= 200; i++ )
    {
        f[ i ] = f[ i - 1 ];
        f[ i ] += f[ i - 2 ];
    }
    scanf("%d", &n);
    while ( n-- )
    {
        scanf("%s", str);
        l = strlen( str );
        printf("%d", f[ l ].num[ f[ l ].len - 1 ]);
        for ( i = f[ l ].len - 2; i >= 0; i-- )
            printf("%04d", f[ l ].num[ i ]);
        printf("\n");
    }
    return 0;
}
